package test;

//给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
//百度百科中最近公共祖先的定义为：
// “对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) {
                return null;

            }
            if (root == q || root == p) {
                return root;

            }
            TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
            TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
            if (leftTree != null && rightTree != null) {
                return root;
            } else if (leftTree != null) {
                return leftTree;
            } else {
                return rightTree;
            }
        }
    }
}

